实现二叉树先序，中序和后序遍历

[编程题]实现二叉树先序，中序和后序遍历

热度指数：4199 时间限制：C/C++ 8秒，其他语言16秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

分别按照二叉树先序，中序和后序打印所有的节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出三行，分别表示二叉树的先序，中序和后序。

示例1

输入

输出

1 2 3
2 1 3
2 3 1

备注:

算法知识视频讲解

Python 3

牛客942266422号

def inorder(root):
    if tree_dict[root][0]:
        inorder(tree_dict[root][0])
    print(root, end=' ')
    if tree_dict[root][1]:
        inorder(tree_dict[root][1])
def preorder(root):
    print(root, end=' ')
    if tree_dict[root][0]:
        preorder(tree_dict[root][0])
    if tree_dict[root][1]:
        preorder(tree_dict[root][1])
def postorder(root):
    if tree_dict[root][0]:
        postorder(tree_dict[root][0])
    if tree_dict[root][1]:
        postorder(tree_dict[root][1])
    print(root, end=' ')
tree_dict = dict()
n, root = tuple(map(int, input().strip().split()))
for i in range(n):
    fa, lch, rch = list(map(int, input().strip().split()))
    tree_dict[fa] = (lch, rch)
preorder(root)
print()
inorder(root)
print()
postorder(root)

发表于 2022-03-14 13:29:05 回复(0)